package com.leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Date250731 {
    public static void main(String[] args) {
        int[] arr = new int[10];
        String s = "abc";
        for(char ch : s.toCharArray()){
            arr[ch - 97]++;
        }
        System.out.println(Arrays.toString(arr));
        System.out.println("==========");

        String ss = "cbaebabacd", pp = "abc";
        Date250731 run = new Date250731();
        System.out.println(run.findAnagrams(ss, pp));
    }
    public List<Integer> findAnagrams1(String ss, String pp) {
        List<Integer> list = new ArrayList<>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        int[] hash1 = new int[26];
        for(char ch : p){
            hash1[ch - 'a']++;
        }
        int[] hash2 = new int[26];
        int m = p.length;
        for(int left = 0, right = 0, count = 0; right < s.length;right++){
            char in = s[right];
            hash2[in - 'a']++;
            if(hash2[in - 'a'] <= hash1[in - 'a']) {
                count++;
            }
            if(right - left + 1 > m){
                char out = s[left];
                left++;
                if(hash2[out - 'a'] <= hash1[out - 'a']){
                    count--;

                }
                hash2[out - 'a']--;
            }
            if(count == m){
                list.add(left);
            }
        }
        return list;
    }

    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> list = new ArrayList<>();
        int[] hash1 = new int[26];//pp
        int[] hash2 = new int[26];
        for(char ch : pp.toCharArray()){
            hash1[ch - 97]++;
        }
        int left = 0, right = 0, len = pp.length();
        for(;right < ss.length(); right++ ){
            hash2[ss.charAt(right) -97]++;
            if(right - left + 1 >= len){
                int ret = check(hash1, hash2);
                if(ret == 1){
                    list.add(left);
                }
                hash2[ss.charAt(left) - 97]--;
                left++;
            }

        }
        return list;

    }
    static int check(int[] hash1, int[] hash2){
        for(int i = 0; i < 26; i++){
            if(hash1[i] != hash2[i])
                return -1;
        }
        return 1;
    }
}
